package zw_401_500.zw_461_汉明距离;

class Solution {
    public static void main(String[] args) {
        int x = 1, y = 4;
        int distance = hammingDistance(x, y);
        System.out.println(distance);
    }


    /**
     * 方法三：Brian Kernighan 算法
     * 时间复杂度：O(logC)，其中 C 是元素的数据范围，在本题中 logC=log2^31=31。
     * 空间复杂度：O(1)。
     *
     * @param x
     * @param y
     * @return
     */
    public static int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }


    /**
     * *法二：移位实现位计数
     * 时间复杂度：O(logC)，其中 C 是元素的数据范围，在本题中 logC=log2^31=31。
     * 空间复杂度：O(1)。
     *
     * @param x
     * @param y
     * @return
     */
//    public static int hammingDistance(int x, int y) {
//        int s = x ^ y, ret = 0;
//        while (s != 0) {
//            ret += s & 1;
//            s >>= 1;
//        }
//        return ret;
//    }


    /**
     * 方法一：内置位计数功能
     * 内置函数
     *
     * @param x
     * @param y
     * @return
     */
//    public static int hammingDistance(int x, int y) {
//        return Integer.bitCount(x ^ y);
//    }


    /**
     * 从后向前，对每一位进行比较，用count计数
     *
     * @param x
     * @param y
     * @return
     */
//    public static int hammingDistance(int x, int y) {
//        if (x == y) return 0;
//        if (x > y) {
//            int temp = x;
//            x = y;
//            y = temp;
//        }
//        int count = 0;
//        while (x < y) {
//            if ((x & 1) != (y & 1)) count++;
//            x >>>= 1;
//            y >>>= 1;
//        }
//        return count;
//    }
}
